This section details the need for the present invention, prior art cryptanalysis methods and the encryption method now used in GSM.
GSM is the most widely spread method of cellular communications. It includes a measure of data protection by encryption, which sometimes it may be desirable to decrypt.
For example, law enforcement agencies, such as the police, may desire to listen to cellular communications, without a physical connection to the cellular infrastructure. This process often requires court permission, and is sometimes referred to as lawful interception.
Customers have a sense of security when using the cellular phone, which sometimes is not justified. Eavesdroppers may listen on a conversation, hijack a call or make phone calls at a user's expense. It may be desirable to test the level of security of the system by performing attempts at attacking the system. The actual level of network security can thus be evaluated. Such tests may be performed by the cellular network provider, by local support entities or customer protection agencies.
The above, as well as other applications, require the performance of cryptanalysis in real time, in a short time period and using a reasonable amount of digital memory, such as has not been achieved in prior art.
GSM is the most widely used cellular technology. By December 2002, more than 787.5 million GSM customers in over 191 countries formed approximately 71% of the total digital wireless market. GSM incorporates security mechanisms. Network operators and their customers rely on these mechanisms for the privacy of their calls and for the integrity of the cellular network. The security mechanisms protect the network by authenticating customers to the network, and provide privacy for the customers by encrypting the conversations while transmitted over the air.
GSM uses encryption to protect transmitted signals. There are two basic methods in use now, A5/1 and A5/2, with the former mostly used in the Middle East and the latter generally for the rest of the world. The A5/1 is more difficult to decrypt without a prior knowledge of the key that has been used.
Thus, to listen to GSM transmissions, it is required to decrypt the messages. The frequency hopping in GSM makes the problem all the more difficult.
There are three main types of cryptographic algorithms used in GSM: A5 is a stream-cipher algorithm used for encryption, A3 is an authentication algorithm and A8 is the key agreement algorithm. The design of A3 and A8 is not specified in the specifications of GSM, only the external interface of these algorithms is specified. The exact design of the algorithm can be selected by the operators independently. However, many operators used the example, called COMP128, given in the GSM memorandum of understanding (MoU).
Prior art cryptanalysis methods pose unrealistic demands, such as a few minutes of known conversation to the bits, see list of references below.
Briceno, Goldberg, and Wagner have performed cryptanalysis of the found COMP128, allowing to find the shared (master) key of the mobile and the network, thus allowing cloning. The description of algorithm A5 is part of the specifications of GSM, but was never made public. There are two currently used versions of A5: A5/1 and A5/2. A5/1 is the “strong” export-limited version. A5/2 is the version that has no export limitations, however it is considered the “weak” version.
The exact design of both A5/1 and A5/2 was reverse engineered by Briceno from an actual GSM telephone in 1999 and checked against known test-vectors. An additional new version, which is standardized but not yet used in GSM networks is A5/3. It was recently chosen, and is based on the block cipher KASUMI.
GPRS (General Packet Radio Service) is a new service for GSM networks that offer ‘always-on’, higher capacity, Internet-based content and packet-based data services, it enables services such as color Internet browsing, e-mail on the move, powerful visual communications, multimedia messages and location-based services. GPRS uses its own cipher, however, the key for the GPRS cipher is created by the same A3A8 algorithm in the subscriber's SIM card, using the same K, as used for creating encryption keys for A5/1, A5/2 and A5/3. We will use this fact to attack it later. A5/1 was initially cryptanalized by Golic, and later by: Biryukov, Shamir and Wagner, Biham and Dunkelman, and recently by Ekdahl and Johansson.
After A5/2 was reverse engineered, it was immediately cryptanalized by Goldberg, Wagner and Green. Their attack is a known plaintext attack that requires the difference in the plaintext of two GSM frames, which are exactly 211 frames apart (about 6 seconds apart). The average time complexity of this attack is approximately 216 dot products of 114-bit vectors.
Apparently, this attack is not applicable (or fails) in about half of the cases, since in the first frame it needs the 11th bit of R4 to be zero after the initialization of the cipher. A later work by Petrovic and Fúster-Sabater suggests to treat the initial internal state of the cipher as variables, write every output bit of the A5/2 algorithm as a quadratic function of these variables, and linearize the quadratic terms. They showed that the output of A5/2 can be predicted with extremely high probability after a few hundreds of known output bits. However, this attack does not discover the session key of A5/2 (Kc).
Thus, it is not possible to use this attack as a building block for more advanced attacks, like those that we present later. The time complexity of this later result is proportional to 217 Gauss eliminations of matrices of size of (estimated) about 400×719.
Goldberg, Wagner and Green presented the first attack on A5/2. The time complexity of this attack is very low. However, it requires the knowledge of the XOR of plaintexts in two frames that are 211 frames apart. Their attack shows that the cipher is quite weak, yet it might prove difficult to implement such an attack in practice. The problem is knowing the exact XOR of plaintexts in two frames that are 6 seconds apart.
Another aspect is the elapsed time from the beginning of the attack to its completion. Their attack takes at least 6 seconds, because it takes 6 seconds to complete the reception of the data. The novel method disclosed in the present application greatly improves the speed of the attack.
The known plaintext attack of Petrovic and Fúster-Sabater have similar data requirements as our attack, however it does not recover the session key (Kc) and, therefore, may not be suitable for the active attacks that we describe later.
The state of prior art can be reviewed in the following references:                1. A pedagogical implementation (in C programming language) of A5/1 and A5/2:        Marc Briceno, Ian Goldberg, David Wagner, A pedagogical implementation of the GSM A5/1 and A5/2 “voice privacy” encryption algorithms, http://cryptome.org/gsm-a512.htm (Originally on www.scard.org), 1999.        2. Description and cryptanalysis of COMP128, used by many GSM operators as A3A8:        Marc Briceno, Ian Goldberg, David Wagner, An implementation of the GSM A3A8 algorithm, http://www.iol.ie/kooltek/a3a8.txt, 1998.        Marc Briceno, Ian Goldberg, David Wagner, GSM Cloning, http://www.isaac.cs.berkeley.edu/isaac/gsm-faq.html, 1998.        3. Known-Plaintext Cryptanalysis of A5/1:        Eli Biham, Orr Dunkelman, Cryptanalysis of the A5/1 GSM Stream Cipher, Progress in Cryptology, proceedings of Indocrypt'00, Lecture Notes in Computer Science 1977, Springer-Verlag, pp. 43-51, 2000.        Alex Biryukov, Adi Shamir, Cryptanalytic Time/Memory/Data Tradeoffs for Stream Ciphers, Advances in Cryptology, proceedings of Asiacrypt'00, Lecture Notes in Computer Science 1976, Springer-Verlag, pp. 1-13, 2000.        Alex Biryukov, Adi Shamir, David Wagner, Real Time Cryptanalysis of A5/1 on a PC, Advances in Cryptology, proceedings of Fast Software Encryption'00, Lecture Notes in Computer Science 1978, Springer-Verlag, pp. 1-18, 2001.        Patrik Ekdahl, Thomas Johansson, Another Attack on A5/1, to be published in IEEE Transactions on Information Theory, http://www.it.lth.se/patrik/publications.html, 2002.        Jovan Golic, Cryptanalysis of Alleged A5 Stream Cipher, Advances in Cryptology, proceedings of Eurocrypt'97, LNCS 1233, pp. 239-255, Springer-Verlag, 1997.        4. A5/2 related information:        Ian Goldberg, David Wagner, Lucky Green, The (Real-Time) Cryptanalysis of A5/2, presented at the Rump Session of Crypto'99, 1999.        Security Algorithms Group of Experts (SAGE), Report on the specification and evaluation of the GSM cipher algorithm A5/2, http://cryptome.org/espy/ETR278e01p.pdf, 1996.        Slobodan Petrovic, Amparo Fúster-Sabater, Cryptanalysis of the A5/2 Algorithm, Cryptology ePrint Archive, Report 2000/052, Available online on http://eprint.iacr.org, 2000.Description of A5/2 and GSM Security Background        
In this section we describe the internal structure of A5/2 and the way it is used, see FIG. 4. A5/2 consists of 4 maximal-length LFSRs: R1, R2, R3, and R4. These registers are of length 19-bit, 22-bit, 23-bit, and 17-bit respectively. Each register has taps and a feedback function. Their irreducible polynomials are: x19⊕x5⊕x2⊕x⊕1, x22⊕x⊕1, x23⊕x15⊕x2⊕x⊕1, and x17⊕x5⊕1, respectively.
Note that we give the bits in the registers in reversed order, i.e., in our numbering scheme, corresponds to a tap in index len−i−1, where len is the absolute register length. For example, when R4 is clocked, the XOR of R4[17−0−1=16] and R4[17−5−1=11] is computed. Then the register is shifted one place to the right, and the value of the XOR is placed in R4[0].
At each step of A5/2 registers R1, R2 and R3 are clocked according to a clocking mechanism that is described later. Then, register R4 is clocked. After the clocking was performed, one output bit is ready at the output of A5/2. The output bit is a non-linear function of the internal state of R1, R2, and R3.
After the initialization 99 bits of output are discarded, and the following 228 bits of output are used as the output key-stream. Some references state that A5/2 discards 100 bits of output, and that the output is used with a one-bit delay. This is equivalent to stating that it discards 99 bits of output, and that the output is used without delay.
Denote Kc[i] as the i'th bit of the 64-bit session-key Kc, Rj[i] the i'th bit of register j, and f[i] the i'th bit of the 22-bit publicly known frame number.
The key-stream generation is as follows:
1. Initialize with Kc and frame number.
2. Force the bits R1[15], R2[16], R3[18], R4[10] to be 1.
3. Run A5/2 for 99 clocks and ignore the output.
4. Run A5/2 for 228 clocks and use the output as key-stream.
The first output bit is defined as the bit that is at the output after the first clocking was performed.
The initialization is done in the following way:                Set all LFSRs to 0 (R1=R2=R3=R4=0).        For i:=0 to 63 do                    1. Clock all 4 LFSRs.            2. R1[0]←R1[0]⊕Kc[i]            3. R2[0]←R2[0]⊕Kc[i]            4. R3[0]←R3[0]⊕Kc[i]            5. R4[0]←R4[0]⊕Kc[i]                        For i:=0 to 21 do                    1. Clock all 4 LFSRs.            2. R1[0]←R1[0]⊕f[i]            3. R2[0]←R2[0]⊕f[i]            4. R3[0]←R3[0]⊕f[i]            5. R4[0]←R4[0]⊕f[i]            In FIG. 4 the internal structure of A5/2 algorithm is showed.                        
The clocking mechanism works as follows: register R4 controls the clocking of registers R1, R2, and R3. When clocking of R1, R2, and R3 is to be performed, bits R4[3], R4[7], and R4[10] are the input of the clocking unit. The clocking unit performs a majority function on the bits. R1 is clocked if and only if R4[10] agrees with the majority. R2 is clocked if and only if R4[3] agrees with the majority. R3 is clocked if and only if R4[7] agrees with the majority. After these clockings, R4 is clocked.
Once the clocking was performed, an output bit is ready. The output bit is computed as follows:
output=R1[18]⊕maj(R1[12],R1[14]⊕1,R1[15])⊕R2[21]⊕maj(R2[9],R2[13],R2[16]⊕1)⊕R3[22]⊕maj(R3[13]⊕1,R3[16],R3[18]), where maj(•,•,•) is the majority function. i.e., out of each register, there are 3 bits whose majority is XORed to form the output (when one bit of each triplet is inverted), in addition to the last bit of each register. Note that the majority function is quadratic in its input: maj(a,b,c)=a·b⊕b·c⊕c·a.
A5/2 is built on a somewhat similar framework of A5/1. The feedback functions of R1, R2 and R3 are the same as A5/1's feedback functions. The initialization process of A5/2 is also somewhat similar to that of A5/1. The difference is that A5/2 also initializes R4, and that after initialization one bit in each register is forced to be 1. Then A5/2 discards 99 bits of output while A5/1 discards 100 bits of output. The clocking mechanism is the same, but the input bits to the clocking mechanism are from R4 in the case of A5/2, while in A5/1 they are from R1, R2, and R3. The designers meant to use similar building blocks to save hardware in the mobile.
This algorithm outputs 228 bits of key-stream. The first block of 114 bits is used as a key-stream to encrypt the link from the network to the customer, and the second block of 114 bits is used to encrypt the link from the customer to the network. Encryption is performed as a simple XOR of the message with the key stream.
Although A5 is a stream cipher, it is used to encrypt 114-bit “blocks”. Each such block is the payload of a GSM burst, which is a GSM air-interface data unit. Note that each frame is constructed of 8 consecutive bursts, serving 8 customers in parallel. Each customer is allocated a burst index. All the bursts in this index are designated for that customer. The frames are sequentially numbered, and each frame has a 22-bit publicly known frame number associated with it. This frame number is used when initializing A5. Since the focus is always on a single customer, we use the terms “burst” and “frame” interchangeably.
One might wonder why does GSM use a stream cipher and not a block cipher of 114-bit block size. A possible explanation is that GSM performs error-correction and then encryption. Assume that one bit in a block is flipped due to an error. Decrypting that block with a block cipher would result in a block that would appear random, and that the error-correction codes have no chance to correct. However, when using a stream cipher, one flipped bit causes exactly one flipped bit after decryption.
GSM Security Background
Following is a more detailed description on the usage and specification of A3 and A8 algorithms.
A3 provides authentication of the mobile to the network, and A8 is used for session-key agreement. The security of these algorithms is based on a user-specific secret key Ki that is common to the mobile and the network. The GSM specifications do not specify the length of Ki, thus it is left for the choice of the operator, but usually it is a 128-bit key. Authentication of the customers to the network is performed using the A3 authentication algorithm as follows: The network challenges the customer with a 128-bit randomly chosen value RAND. The customer computes a 32-bit long response SRES=A3(Ki,RAND), and sends SRES to the network, which can then check its validity.
The session key Kc is obtained by the A8 algorithm as follows: Kc=A8(Ki,RAND). Note that A8 and A3 are always invoked together and with the same parameters. In most implementations, they are one algorithm with two outputs, SRES and K. Therefore, they are usually referred to as A3A8.
The above description of prior art encryption in GSM is relayed upon in the detailed description of the invention below.
In this inventions the term cryptanalysis is used to describe the process of being able to encrypt/decrypt communication without the prior knowledge of the used session key. In some cases, the cryptanalysis can retrieve the session key that is used. In other cases the session key is not retrieved, however it might still be possible to decrypt or encrypt messages in the same way that would have been if the relevant cipher were used using the session key. Sometimes in this invention the term decryption is also used in the meaning of cryptanalysis.
Known plaintext means that the attacker has access to encrypted messages as well as to the messages that were encrypted.
Ciphertext only means that the attacker has access only to the encrypted messages, and has no access to the messages before they were encrypted.
In this invention the term phone should be understood in the broader sense of a cellular device using the GSM network.